#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define False 0
#define True 1
const int MAX_GROUP = 5000;
unsigned int SEED = 1;
// 顺序遗传算法

void initialize_population(int generation_num);
void evaluate_population(int generation_num);

int termination_condition = False;

typedef struct {
    // char dirty:1;
    int x:21;
    int y:21;
    int z:21;
} Personal;


void transfer(int64_t n, long *x, long *y, long *z){
    int64_t msk = 0x1fffff ;
    int flag;
    // printf("msk = %lx\n", msk);
    Personal p;
    // printf("%d", sizeof(Personal));
    // Personal p = (Personal)n;


    *z = (n & msk);
    *z = (*z >> 20) == 1 ? (~(*z)) + (1<<20) + 1: *z;

    n = n >> 21;
    *y = (n & msk);
    *y = (*y >> 20) == 1 ? ~(*y) + (1<<20) + 1 : *y;

    n = n >> 21;
    *x = (n & msk);
    *x = (*x >> 20) == 1 ? ~(*x) + (1<<20) + 1 : *x;
    // printf("x = %ld, y = %ld, z = %ld\n", *x, *y, *z);
}
long function(long x, long y, long z){
    return -x*x + 1000000 * x - y*y - 40000 * y - z*z;
}

long evaluation(long n){
    long x, y, z;
    transfer(n, &x, &y, &z);
    return function(x, y, z);

};

int Rand(int x, int y){
    
    srand(SEED++);
    int b = x, d = y - x + 1;
    return (int)(1.0 * rand() * d / RAND_MAX + b);
}

void singlePoint(long f, long m, long *c1, long *c2){
    int point = Rand(1, 63);
    // printf("point = %d \n", point);
    long msk = (1L << point) - 1;
    // printf("f = %lx, m = %lx  msk = %lx  ", f, m, msk);
    // printf("%ld, %ld \n", f & msk, m & ~msk);
    *c1 = (f & msk) + (m & ~msk);
    *c2 = (f & ~msk) + (m & msk);
}

int main(int argc, char **argv ){
    time_t t;
    SEED = (unsigned)time(&t);
    int generation_num = 0; 
    //生成初始种群
    int64_t group[MAX_GROUP], value[MAX_GROUP], next_group[MAX_GROUP];
    for(int i = 0; i < MAX_GROUP; i++){
        long r1 = 0, r2 = 0;
        while (r1 == 0L) r1 = (long)rand();
        while (r2 == 0L) r2 = (long)rand();
        
        group[i] = (r1 << 32) + r2;
        // value[i] = evaluation(group[i]);
    }
    printf("%ld \n", evaluation(0b001000000000100001000000000100000010100000100000000010000001000));
    ;
    long x,y,z;
    transfer(0b001000000000100001000000000100000010100000100000000010000001000 ,&x, &y, &z);
    // for(int i = 0; i < MAX_GROUP; i++) {
    //     long x, y, z;
    //     transfer(group[i], &x, &y, &z);
    //     printf(" %016lx  (%d, %d, %d)\n", group[i], x, y, z);
    //     // printf("%ld, ", evaluation(group[i]));
        
    // }
    while(! termination_condition){
        //随机化


        //选择双亲  淘汰
        for(int i = 0; i * 2 < MAX_GROUP; i++){
            int father, mather;
            // father = evaluation(group[i]) < evaluation(group[i+1]) ? i : i + 1;
            // mather = evaluation(group[i+2]) < evaluation(group[i +3]) ? i + 2 : i + 3;
            //每个个题都随机选择

            int p1 = Rand(0, MAX_GROUP), p2 = Rand(0, MAX_GROUP), p3 = Rand(0, MAX_GROUP), p4 = Rand(0, MAX_GROUP);
            // printf("p1 = %d, p2 = %d, p3 = %d, p4 = %d \n", p1, p2, p3, p4);
            father = evaluation(group[p1]) > evaluation(group[p2]) ? p1 : p2;
            mather = evaluation(group[p3]) > evaluation(group[p4]) ? p3 : p4;

            //生成后代  每对父母生成两个孩子  
            long c1, c2;
            //单点交叉
            singlePoint(group[father], group[mather], &c1, &c2);
            // printf("c1 = %d, c2 = %d", c1, c2);

            //突变  随机选择一位进行突变
            c1 = c1 ^ (1 << Rand(0, 63));
            c1 = c1 ^ (1 << Rand(0, 63));
            next_group[i*2] = c1; next_group[i * 2 + 1] = c2;

        }

        // printf("hello world");
        //测试终止条件
        for (int i = 0; i < MAX_GROUP; i++) group[i] = next_group[i];
        generation_num++;
        if (generation_num > 10000) termination_condition = True;
    }
    printf("\n");
    for(int i = 0; i < 100; i++) {
        long x, y, z;
        transfer(group[i], &x, &y, &z);
        printf("(%d, %d, %d) val = %ld \n", x, y, z, evaluation(group[i]));
        // printf("%ld, ", evaluation(group[i]));
        
    }
}

